package com.cat.dataStructure02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/
 * @create 2025/10/13 17:37
 * @since JDK17
 */

public class Solution11 {
    int[] f = new int[1001];
    boolean dfs(char[] s, int cur, int target, int sum) {
        if (cur == s.length) {
            return sum == target;
        }
        int x = 0;
        for (int i = cur; i < s.length; i++) { // 开始划分
            x = x * 10 + s[i] - '0';
            if (dfs(s, i + 1, target, sum + x)) {
                return true;
            }

        }
        return false;
    }

    public int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            char[] s = String.valueOf(i * i).toCharArray();
            if (f[i] == 1 || dfs(s, 0, i, 0)) {
                f[i] = 1;
                ans += i * i;
            }
        }

        return ans;
    }
}
